package demo.Time;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/*
    0-9999个数中有一个缺失，一个重复
    找出缺失和重复的数
 */
public class SpaceToTime {
    public static void main(String[] args) {
        //拿到数据
        Integer[] arr = getData(10000);

        long start = System.currentTimeMillis();
        //开始找重复和缺失的数
        //这里我们用空间换时间，我们创建一个int[]来存取这里面的数，顺便找出缺失和重复的数
        int[] brr = new int[arr.length];

        for (int i = 0; i < arr.length; i++) {
            //这里我们把arr里的每一个数都存到brr里，但是存入的数要和brr的索引对应起来
            brr[arr[i]]++;
            //arr[i]是容器里的随机数
            //brr[]
        }

        for (int i = 0; i < brr.length; i++) {
            if (brr[i] == 0) {
                System.out.println("缺失的数是：" + i);
            } else if (brr[i] == 2) {
                System.out.println("重复的数是：" + i);
            }
        }
        long end = System.currentTimeMillis();

        System.out.println("耗时:" + (end - start));
    }

    private static Integer[] getData(int number) {
        Integer[] arr = new Integer[number];
        for (int i = 0; i < number; i++) {
            arr[i] = i;
        }

        //制造一个缺失的数
        Random r = new Random();
        int lose = r.nextInt(number);

        //制造一个重复的数
        int repeat = r.nextInt(number);

        arr[lose] = repeat;


//        System.out.println(lose);
//        System.out.println(repeat);

        //将数组转换成集合，便于用集合的打乱顺序的方法
        List<Integer> list = Arrays.asList(arr);

        //打乱顺序
        Collections.shuffle(list);

        return arr;
    }
}
